package com.fengdi.everyday.middle;

import java.util.Arrays;

/**
 * @Description 474 一和零
 * @Date 10:02
 */
public class FindMaxForm {
    class ZO {
        int zeros;
        int ones;

        ZO() {
            this.ones = 0;
            this.zeros = 0;
        }
    }

    public int findMaxForm(String[] strs, int m, int n) {
        int len = strs.length;
        int[][][] dp = new int[len + 1][m + 1][n + 1];
        for(int i = 1; i <= len; i++) {
            ZO zerosAndOnes = this.getZO(strs[i - 1]);
            for(int j = 0; j <= m; j++) {
                for(int k = 0; k <= n; k++) {
                    dp[i][j][k] = dp[i - 1][j][k];
                    if(zerosAndOnes.zeros <= j && zerosAndOnes.ones <= k) {
                        dp[i][j][k] = Math.max(
                                dp[i][j][k],
                                dp[i - 1][j - zerosAndOnes.zeros][k - zerosAndOnes.ones] + 1
                        );
                    }
                }
            }
        }

        return dp[len][m][n];
    }

    private ZO getZO(String s) {
        ZO x = new ZO();
        for(char c : s.toCharArray()) {
            if(c == '0') {
                x.zeros++;
            }else {
                x.ones++;
            }
        }

        return x;
    }
}
